PathwaySim

L'obiettivo di questo progetto è quello di trovare le similarità tra le pathway biologiche utilizzando l'algoritmo SimRank.

I dati che si hanno a disposizioni sono presenti all'interno dei seguenti file:

SimRank è una misura di similarità generale, basata su un modello di teoria dei grafi semplice e intuitivo. SimRank è applicabile in qualsiasi dominio con relazioni oggetto-oggetto, che misura la somiglianza del contesto strutturale in cui si verificano gli oggetti, in base alle loro relazioni con altri oggetti. In effetti, SimRank è una misura che dice "due oggetti sono considerati simili se sono referenziati da oggetti simili". Sebbene SimRank sia ampiamente adottato, può produrre punteggi di somiglianza irragionevoli che sono influenzati da diversi fattori.

Premessa

La proposta originale di SimRank suggeriva di scegliere il fattore di decadimento $C = 0,8$ e un numero fisso $K = 5$ di iterazioni da eseguire. Tuttavia, la recente ricerca di D. Lizorkin, P. Velikhov, M. Grinev e D. Turdako http://modis.ispras.ru/Lizorkin/Publications/simrank_accuracy.pdf ha mostrato che i valori dati per $C$ e $K$ generalmente implicano punteggi relativamente bassi dei SimRank calcolati in modo iterativo. Per garantire risultati di calcolo più accurati, quest'ultimo documento suggerisce di utilizzare un fattore di decadimento più piccolo (in particolare, $C = 0,6$) o di eseguire più iterazioni.

Equazione SimRank di base

Per un nodo $v$ in un grafo orientato, indichiamo con $I(v)$ e $O(v)$ l'insieme dei vicini in e out di $v$, rispettivamente. I singoli in-neighbors sono indicati come $I_i(v)$, per $1 \le i \le \left|I(v)\right|$, e i singoli out-neighbors sono indicati come $O_i(v)$, per $1 \le i \le \left|O(v)\right|$.

Indichiamo la somiglianza tra gli oggetti $a$ e $b$ con $s(a, b) \in [0, 1]$. Seguendo la motivazione precedente, viene scritta un'equazione ricorsiva per $s(a, b)$.

Se $a = b$ allora $s(a, b)$ è definito come $1$.

Altrimenti:

$s(a, b) = \frac{C}{\left|I(a)\right| \left|I(b)\right|} \sum_{i=1}^{\left|I(a)\right|}\sum_{j=1}^{\left|I(b)\right|} s(I_i(a), I_j(b))$


dove $C$ è una costante tra $0$ e $1$.
Un problema qui è che $a$ o $b$ potrebbero non avere alcun in-vicino. Poiché non c'è modo di dedurre alcuna somiglianza tra $a$ e $b$ in questo caso, la somiglianza è impostata su $s(a, b) = 0$ , quindi la somma nell'equazione precedente è definita come $0$ quando $I(a) = \emptyset$ o $I(b) = \emptyset$ .

È stato realizzato un programma in Scala che utilizza Spark, per il calcolo distribuito, che calcola il SimRank utilizzando la definizione sopra, di seguito è riportato un esempio.

Esempio

Prima di tutto bisogna compilare utilizzando maven.

$ mvn package install

A questo punto è possibile eseguire l'esempio utilizzando l'istruzione successiva.

Il risultato ottenuto differisce da quello reale per il problema mostrato nella premessa, la soluzione iterativa restituisce un valore più basso di quello originale.

Rappresentazione matriciale di SimRank

Sia $\mathbf{S}$ la matrice di somiglianza la cui voce $[\mathbf{S}]_{a,b}$ denota il punteggio di somiglianza $s(a, b)$, e $\mathbf{A}$ sia la colonna normalizzata [[matrice di adiacenza]] la cui voce $[\mathbf{A}]_{a,b}=\frac{1}{|\mathcal{I}(b)|}$ se c'è un arco da $a$ a $b$ e 0 altrimenti. Quindi, nelle notazioni matriciali, SimRank può essere formulato come:

${{\mathbf{S}}}= \max\{C\cdot (\mathbf{A}^{T} \cdot {{\mathbf{S}}}\cdot {{\mathbf{A}}} ) , {{\mathbf{I}}}\},$

dove $\mathbf{I}$ è una matrice identità.

Esempio

Seguendo la definizione riportata sopra effettuiamo il calcolo utilizzando la notazione matriciale con Scala, Spark e Hadoop.

Dopo aver introdotto il SimRank e alcune delle sue implementazioni, di seguito sono importate le librerie e le funzioni necessarie per ogni cella.

Nella risoluzione del problema per il calcolo del SimRank non verranno utilizzate le implementazioni in Scala, questo perché sono più efficienti se utilizzate in un cluster dato che si è utilizzato Spark e Hadoop. Per semplicità verrà utilizzata la libreria networkx di Python, che ha al proprio interno una funzione che permette di calcolare il SimRank.

SimRankLowrank

Questa è un'altra implementazione che riesce a stimare il valore reale del SimRank in grafi molto grandi.

L'implementazione non è stata fatta da me, per questo non è riportato il codice sorgente all'interno della repository di GitHub, ma può essere consultato al seguente link.

Di seguito è riportato un esempio, successivamente verrà utilizzato anche per verificare se è possibile utilizzare questa implementazione veloce per risolvere il problema delle similarità tra le pathway biologiche.

SimRank con approccio naive

Eseguire l'approssimazione SimRank lowrank

L'approssimazione segue la seguente equazione:

$$ \tilde{S} = I + C^{\top}C - \text{diag}(C^{\top}C) + UDU^{\top}. $$

La matrice $C$ è la matrice di adiacenza normalizzata per colonne e scalata per $\sqrt{c}$ del grafo. La matrice $U$ è di basso rango e la matrice $D$ è diagonale.

NetworkX

Di seguito è riportato un esempio del calcolo del SimRank utilizzando networkx.

Similarità tra le pathway biologiche

Prima di tutto creaiamo il grafo utilizzando tutti gli edges che sono presenti all'interno del file ./data/gene_edges.tsv.

Successivamente all'interno del grafo verranno introdotte le pathway lette nel file ./data/pathways.tsv. Gli elementi che otterremo sono:

Gli ultimi due dizionari sono utili per effettuare delle conversioni.

A questo punto tutti i nodi vengono mappati in modo da avere dei valori che vanno da 0 a n-1, dove n è il numero dei nodi. Questo viene fatto perché semplificherà la rappresentazione della matrice di similarità tra i vari elementi.

Viene creato un grafo che mantiene gli edges precedenti, ma dove ogni nodo ha come id quello del mappping.

Per eseguire il SimRank con networkx è possibile utilizzare le righe di codice sotto, basta levare i commenti. Il processo impiegherà un po' di tempo, proprio per questo motivo il risultato è stato già ottenuto e salvato su un file csv e su un json.

Il risultato sopra restituisce la differenza come norma di Frobenius tra il SimRank calcolato da networkx e quello approssimato dal SimRank-lowrank. Quello che osserviamo è che il risultato è accettabile, quindi se non si vuole perdere molto trempo la scelta migliore è il SimRank-lowrank.

Rappresentazione grafo di similarità

A questo punto possiamo rappresentare visivamente le similarità tra le pathway biologiche all'interno del grafo considerato.

Prima bisogna effettuare un mapping tra i nomi delle pathway e gli id del grafo.